When using the traditional resilience methods in Internet Protocol (IP) networks, the re-routing of traffic around a failure can take a significant time. A primary reason for this slow reconfiguration is the reactive approach offered by conventional routing protocols, such as Open Shortest Path First (OSPF) or the Intermediate System-to-Intermediate System (IS-IS) routing protocol, which are widely deployed in modern IP networks. With existing protocols, fault recovery is assured by propagating the information about the failure in the network and re-computing the routing tables at each router. This is accomplished after a failure exists which increases the time necessary for re-routing a packet.
In contrast to traditional IP error correction techniques, which are fundamentally reactive, the new IP Fast Reroute (IPFRR) framework standardized in the Routing working group of Internet Engineering Task Force (IETF) proposes proactive solutions. Thus, these methods are always ready to reroute packets. However, the reroute must be conducted locally through algorithms because there is no time for any communication. By using these algorithms, transient link errors may also be avoided. Since packets can reach the destination, the starting of the reconfiguration of the network can be delayed until the failure is verified.
Among the IPFRR techniques, methods using Not-via addresses are important in accomplishing re-routes. These methods use simple IP-in-IP tunnels to avoid a single failed resource, which is an inexpensive operation in current routers. The resource may be either a node or a link. If there is more than one failure, packets may not reach the destination. In such a situation, packets may be dropped, thereby preventing the formation of a loop.
Two redundant trees may be directed at spanning trees rooted at an arbitrary given node (root node) in such a way that there is a path from each node to the root on both trees. These paths are ‘node-disjointed’ to provide separate paths utilizing different nodes. Redundant trees can always be found, even in linear time, if the network is two-node connected. Thus, these trees may be used for resilience if the destination is the root node. Furthermore, if the graph used in defining the pathways of the packet is not two-node connected, two directed trees may be found in such a way that the two paths from any of the nodes to the root are maximally node and edge disjointed. These trees are known as maximally redundant trees and may also be found in linear time by a simple modification of the algorithm finding redundant trees. If a network is two-node-connected, perfect redundancy can be achieved since maximally redundant trees are also redundant trees. Furthermore, it is also possible to compute the next hops of two redundant trees. The necessary parts of the trees for resilience are rooted at each node as a root in linear time.
However, there are problems with the existing methods. The rerouting time of conventional routing protocols is too long. Studies have shown that using OSPF or IS-IS, rerouting time can take numerous seconds or longer in extreme cases. Gigabytes of data may be lost during this time period. Additionally, users of applications or the applications themselves may even lose their sessions. Obviously, for real time traffic, such as Internet Protocol Television (IPTV) or Voice over IP (VoIP), this slow response is even more undesirable.
The greatest problem of the simplest IPFRR techniques is that they can correct failures only in special cases (e.g., when multiple equal cost shortest paths (like in ECMP) or multiple loop free alternate paths exist to the destination).
Currently, there are only two IPFRR methods which can provide one hundred percent link fault recovery, Failure Insensitive Routing (FIR) and Not-via Addresses. However, neither of these techniques can always provide fast resilience when more than one failure occurs simultaneously.
The original FIR is prone to create loops when more than one link or, at least one node has failed. A loop is a forwarding cycle which is never left by packets. Packets are dropped when Time-To-Live (TTL) is up. There is a solution which can avoid these loops. However, when the loops are avoided, the paths used when no failure exists must generally be longer then the shortest paths.
The existing Not-via addresses also suffers from some disadvantages. Although Not-via Addresses uses the shortest paths when no failures are present, numerous IP addresses are used in order to avoid a failed resource if necessary. In such circumstances, the number of IP addresses scales quadratically. This high number of IP addresses raises the problem of managing these addresses. Furthermore, utilizing a Not-via method also increases the computational complexity. This method needs numerous shortest path computations. Thus, the time needed to download the computed routings to the line cards of the routers is also increased because of the high number of addresses. Additionally, a Not-via method utilizes several special cases, thereby making it difficult to debug and implement.